# search.py
# ---------
# Licensing Information: Please do not distribute or publish solutions to this
# project. You are free to use and extend these projects for educational
# purposes. The Pacman AI projects were developed at UC Berkeley, primarily by
# John DeNero (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu).
# For more info, see http://inst.eecs.berkeley.edu/~cs188/sp09/pacman.html

"""
In search.py, you will implement generic search algorithms which are called 
by Pacman agents (in searchAgents.py).
"""

import util

class SearchProblem:
  """
  This class outlines the structure of a search problem, but doesn't implement
  any of the methods (in object-oriented terminology: an abstract class).
  
  You do not need to change anything in this class, ever.
  """
  
  def getStartState(self):
     """
     Returns the start state for the search problem 
     """
     util.raiseNotDefined()
    
  def isGoalState(self, state):
     """
       state: Search state
    
     Returns True if and only if the state is a valid goal state
     """
     util.raiseNotDefined()

  def getSuccessors(self, state):
     """
       state: Search state
     
     For a given state, this should return a list of triples, 
     (successor, action, stepCost), where 'successor' is a 
     successor to the current state, 'action' is the action
     required to get there, and 'stepCost' is the incremental 
     cost of expanding to that successor
     """
     util.raiseNotDefined()

  def getCostOfActions(self, actions):
     """
      actions: A list of actions to take
 
     This method returns the total cost of a particular sequence of actions.  The sequence must
     be composed of legal moves
     """
     util.raiseNotDefined()
           

def tinyMazeSearch(problem):
  """
  Returns a sequence of moves that solves tinyMaze.  For any other
  maze, the sequence of moves will be incorrect, so only use this for tinyMaze
  """
  from game import Directions
  s = Directions.SOUTH
  w = Directions.WEST
  return  [s,s,w,s,w,w,s,w]

'''
def depthFirstSearch(problem):
  """
  Search the deepest nodes in the search tree first
  [2nd Edition: p 75, 3rd Edition: p 87]
  
  Your search algorithm needs to return a list of actions that reaches
  the goal.  Make sure to implement a graph search algorithm 
  [2nd Edition: Fig. 3.18, 3rd Edition: Fig 3.7].
  
  To get started, you might want to try some of these simple commands to
  understand the search problem that is being passed in:
  
  print "Start:", problem.getStartState()
  print "Is the start a goal?", problem.isGoalState(problem.getStartState())
  print "Start's successors:", problem.getSuccessors(problem.getStartState())
  """
  "*** YOUR CODE HERE ***"
  closed = set()
  semiclosed = set() # to keep track of nodes visited but not expanded
  fringe = util.Stack()
  fringe.push([(problem.getStartState(), None, None), ((None, None), None, None)]) # root has no parent
  actionsSoFar = []
  
  while True:
    if fringe.isEmpty():
        return None
    node = fringe.pop()
    currentTriple = node[0]
    currentNode = currentTriple[0]
    parentTriple = node[1]
    parentNode = parentTriple[0]
    actionsSoFar = actionsSoFar + [currentTriple[1]]

    if problem.isGoalState(currentNode):
        return actionsSoFar[1:]

    if set([currentNode]).issubset(closed) == False:
       closed.add(currentNode)
       #find parent node among successors and add it first to the stack
       queue = util.Queue()
       successorsList = problem.getSuccessors(currentNode)
       for triple in successorsList:
           if triple[0] == parentNode:
               fringe.push([triple, currentTriple])
               continue
           # if the successor is in the closed set, don't need to visit it
           if set([triple[0]]).issubset(closed) | set([triple[0]]).issubset(semiclosed) == True:
               continue
           queue.push([triple, currentTriple])
           # add all successors except the one that'll be expanded next to the closed set
           if successorsList.index(triple) != len(successorsList) - 1:
               semiclosed.add(triple[0])
       while queue.isEmpty() == False:
           fringe.push(queue.pop())'''
'''  util.raiseNotDefined()'''

# foodsearchproblem version
def depthFirstSearch(problem):
  """
  Search the deepest nodes in the search tree first
  [2nd Edition: p 75, 3rd Edition: p 87]
  
  Your search algorithm needs to return a list of actions that reaches
  the goal.  Make sure to implement a graph search algorithm 
  [2nd Edition: Fig. 3.18, 3rd Edition: Fig 3.7].
  
  To get started, you might want to try some of these simple commands to
  understand the search problem that is being passed in:
  
  print "Start:", problem.getStartState()
  print "Is the start a goal?", problem.isGoalState(problem.getStartState())
  print "Start's successors:", problem.getSuccessors(problem.getStartState())
  """
  "*** YOUR CODE HERE ***"
  closed = set()
  semiclosed = set() # to keep track of nodes visited but not expanded
  fringe = util.Stack()
  fringe.push([(problem.getStartState(), None, None), ((None, None), None, None)]) # root has no parent
  actionsSoFar = []
  prevNode = ((None, None), None, None)
  
  while True:
    if fringe.isEmpty():
        return None
    node = fringe.pop()
    currentTriple = node[0]
    currentNode = currentTriple[0]
    currentLocation = currentNode[0]
    parentTriple = node[1]
    parentNode = parentTriple[0]
    parentLocation = parentNode[0]
#    tweakNodeState() to handle the issue of number of dots on the grid
    if prevNode[1] != None:
        nextFood = prevNode[1].copy()
        nextFood[currentLocation[0]][currentLocation[1]] = False
        currentNode = ((currentLocation[0], currentLocation[1]), nextFood)
    
    actionsSoFar = actionsSoFar + [currentTriple[1]]
    print currentTriple[1]

    if problem.isGoalState(currentNode):
        return actionsSoFar[1:]

    if set([currentLocation]).issubset(closed) == False:
       closed.add(currentLocation)
       #find parent node among successors and add it first to the stack
       queue = util.Queue()
       successorsList = problem.getSuccessors(currentNode)
       for triple in successorsList:
           if triple[0][0] == parentLocation:
               fringe.push([triple, currentTriple])
               continue
           # if the successor is in the closed set, don't need to visit it
           if set([triple[0][0]]).issubset(closed) | set([triple[0][0]]).issubset(semiclosed) == True:
               continue
           queue.push([triple, currentTriple])
           # add all successors except the one that'll be expanded next to the closed set
           if successorsList.index(triple) != len(successorsList) - 1:
               semiclosed.add(triple[0][0])
       while queue.isEmpty() == False:
           fringe.push(queue.pop())
    prevNode = currentNode
'''  util.raiseNotDefined()'''

'''
def recursiveDepthFirstSearch(node, problem):
    if problem.isGoalState(node):
        return [node]
    else:
        for triple in problem.getSuccessors(node):
            successor = triple[0]
            action = triple[1]
            result = recursiveDepthFirstSearch(successor, problem)
            if result != failure:
                return [action] + result
'''

def breadthFirstSearch(problem):
  """
  Search the shallowest nodes in the search tree first.
  [2nd Edition: p 73, 3rd Edition: p 82]
  """
  "*** YOUR CODE HERE ***"
  from game import Directions
  import bfsagent

  b = bfsagent.bfsagent()

  return b.getActions(problem)
'''  util.raiseNotDefined()'''
      
def uniformCostSearch(problem):
  "Search the node of least total cost first. "
  "*** YOUR CODE HERE ***"
  closed = set()
  fringe = util.PriorityQueue();
  dummyNode = [(None, None, 0), (None, None, 0), 0]
  temp = [(problem.getStartState(), None, 0), dummyNode, 0]
  fringe.push(temp, 0) # root has no parent
  
  while True:
    if fringe.isEmpty():
        return None
    node = fringe.pop()
    currentTriple = node[0]
    currentNode = currentTriple[0] # change notation. it's pretty confusing
    backwardCostOfParent = node[2]
    prevNode = node[1]
    parentTriple = prevNode[0]
    parentNode = parentTriple[0]

    if problem.isGoalState(currentNode):
        tempNode = node
        tempTriple = tempNode[0]
        
        actionsSoFar = []
        while tempTriple[1] != None:
            actionsSoFar = [tempTriple[1]] + actionsSoFar
            tempNode = tempNode[1] # parent
            tempTriple = tempNode[0]
        return actionsSoFar #change it to 1:

    if set([currentNode]).issubset(closed) == False:
       closed.add(currentNode)
       #find parent node among successors and ignore it
       successorsList = problem.getSuccessors(currentNode)
       for triple in successorsList:
           if triple[0] == parentNode:
               continue
           backwardCost = backwardCostOfParent + triple[2]
           fringe.push([triple, node, backwardCost], backwardCost)
'''  util.raiseNotDefined()'''

def nullHeuristic(state, problem=None):
  """
  A heuristic function estimates the cost from the current state to the nearest
  goal in the provided SearchProblem.  This heuristic is trivial.
  """
  return 0

def aStarSearch(problem, heuristic=nullHeuristic):
  "Search the node that has the lowest combined cost and heuristic first."
  "*** YOUR CODE HERE ***"
  util.raiseNotDefined()
    
  
# Abbreviations
bfs = breadthFirstSearch
dfs = depthFirstSearch
astar = aStarSearch
ucs = uniformCostSearch
